<html>
 <head>
  <meta charset="utf-8"/>
  <meta content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no" name="viewport"/>
  <title>
   张驰原: “支持向量机系列”的番外篇一: Duality  | 数螺 | NAUT IDEA
  </title>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" rel="stylesheet"/>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet"/>
  <style type="text/css">
   #xmain img {
                  max-width: 100%;
                  display: block;
                  margin-top: 10px;
                  margin-bottom: 10px;
                }

                #xmain p {
                    line-height:150%;
                    font-size: 16px;
                    margin-top: 20px;
                }

                #xmain h2 {
                    font-size: 24px;
                }

                #xmain h3 {
                    font-size: 20px;
                }

                #xmain h4 {
                    font-size: 18px;
                }


                .header {
	           background-color: #0099ff;
	           color: #ffffff;
	           margin-bottom: 20px;
	        }

	        .header p {
                  margin: 0px;
                  padding: 10px 0;
                  display: inline-block;  
                  vertical-align: middle;
                  font-size: 16px;
               }

               .header a {
                 color: white;
               }

              .header img {
                 height: 25px;
              }
  </style>
  <script src="http://cdn.bootcss.com/jquery/3.0.0/jquery.min.js">
  </script>
  <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript">
   MathJax.Hub.Config({
          tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
          TeX: {equationNumbers: {autoNumber: "AMS"}}
        });
  </script>
  <script src="http://nautstatic-10007657.file.myqcloud.com/static/css/readability.min.js" type="text/javascript">
  </script>
  <script type="text/javascript">
   $(document).ready(function() {
                 var loc = document.location;
                 var uri = {
                  spec: "http://cos.name/2014/03/svm-series-add-1-duality/",
                  host: "http://cos.name",
                  prePath: "http://cos.name",
                  scheme: "http",
                  pathBase: "http://cos.name/"
                 };
    
                 var documentClone = document.cloneNode(true);
                 var article = new Readability(uri, documentClone).parse();
     
                 document.getElementById("xmain").innerHTML = article.content;
                });
  </script>
  <!-- 1466461814: Accept with keywords: (title(0.25):门户网站,统计学,原,服务平台,中国,机,番外篇,向量, topn(0.366666666667):约束条件,统计学,R语言,条件,数据挖掘,性质,形式,下界,中文论坛,时间序列,文章,情况,可视化,数据,这样一来,向量,式子,系数,函数,问题,随机,优化,会议,番外篇,简要地,评论,论坛,时候,极值,不等号).-->
 </head>
 <body class="single single-post postid-9682 single-format-standard sidebar" onload="">
  <div class="header">
   <div class="container">
    <div class="row">
     <div class="col-xs-6 col-sm-6 text-left">
      <a href="/databee">
       <img src="http://nautidea-10007657.cos.myqcloud.com/logo_white.png"/>
      </a>
      <a href="/databee">
       <p>
        数螺
       </p>
      </a>
     </div>
     <div class="hidden-xs col-sm-6 text-right">
      <p>
       致力于数据科学的推广和知识传播
      </p>
     </div>
    </div>
   </div>
  </div>
  <div class="container text-center">
   <h1>
    张驰原: “支持向量机系列”的番外篇一: Duality
   </h1>
  </div>
  <div class="container" id="xmain">
   <div class="hfeed site" id="page">
    <header class="site-header" id="masthead" role="banner">
     <div id="cos-logo">
      <a href="http://cos.name/">
       <img src="http://cos.name/wp-content/themes/COS-kermesinus/images/headers/cos-logo.png"/>
      </a>
     </div>
     <div class="navbar" id="navbar">
      <nav class="navigation main-navigation" id="site-navigation" role="navigation">
       <h3 class="menu-toggle">
        菜单
       </h3>
       <a class="screen-reader-text skip-link" href="http://cos.name/2014/03/svm-series-add-1-duality/#content" title="跳至内容">
        跳至内容
       </a>
       <div class="menu-%e6%88%91%e7%9a%84%e8%8f%9c%e5%8d%95-container">
        <ul class="nav-menu" id="menu-%e6%88%91%e7%9a%84%e8%8f%9c%e5%8d%95">
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-home menu-item-4746" id="menu-item-4746">
          <a href="http://cos.name">
           主页
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-has-children menu-item-8120" id="menu-item-8120">
          <a href="http://cos.name/cn">
           论坛
          </a>
          <ul class="sub-menu">
           <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8124" id="menu-item-8124">
            <a href="http://cos.name/cn/wp-login.php?action=register">
             论坛注册
            </a>
           </li>
           <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8125" id="menu-item-8125">
            <a href="http://cos.name/cn/wp-login.php">
             论坛登录
            </a>
           </li>
          </ul>
         </li>
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-8110" id="menu-item-8110">
          <a href="http://cos.name/books/">
           图书资料
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8112" id="menu-item-8112">
          <a href="http://cos.name/videos">
           视频教程
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8333" id="menu-item-8333">
          <a href="http://cos.name/salon/">
           统计沙龙
          </a>
         </li>
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-8111" id="menu-item-8111">
          <a href="http://cos.name/chinar/">
           R语言会议
          </a>
         </li>
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-8109" id="menu-item-8109">
          <a href="http://cos.name/training/">
           讲座与培训
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8115" id="menu-item-8115">
          <a href="http://cos.name/cn/forum/comprehensive/job/">
           招聘信息
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-has-children menu-item-4780" id="menu-item-4780">
          <a href="http://cos.name/about">
           关于我们
          </a>
          <ul class="sub-menu">
           <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8113" id="menu-item-8113">
            <a href="http://cos.name/2008/11/how-to-work-with-cos/">
             加入我们
            </a>
           </li>
           <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8119" id="menu-item-8119">
            <a href="http://cos.name/donate/">
             赞助我们
            </a>
           </li>
           <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-8114" id="menu-item-8114">
            <a href="http://cos.name/cn/forum/26">
             项目合作
            </a>
           </li>
          </ul>
         </li>
        </ul>
       </div>
       <form action="http://cos.name/" class="search-form" method="get" role="search">
        <label>
         <span class="screen-reader-text">
          搜索：
         </span>
        </label>
       </form>
      </nav>
      <!-- #site-navigation -->
     </div>
     <!-- #navbar -->
    </header>
    <!-- #masthead -->
    <div class="site-main" id="main">
     <div class="content-area" id="primary">
      <div class="site-content" id="content" role="main">
       <article class="post-9682 post type-post status-publish format-standard hentry category-featured category-dmml tag-duality tag-803 tag-514" id="post-9682">
        <header class="entry-header">
         <h1 class="entry-title">
          “支持向量机系列”的番外篇一: Duality
         </h1>
         <div class="entry-meta">
          <span class="date">
           <a href="http://cos.name/2014/03/svm-series-add-1-duality/" rel="bookmark" title="链向“支持向量机系列”的番外篇一: Duality的固定链接">
            <time class="entry-date" datetime="2014-03-19T13:10:08+00:00">
             2014/03/19
            </time>
           </a>
          </span>
          <span class="categories-links">
           <a href="http://cos.name/category/website/featured/" rel="category tag">
            推荐文章
           </a>
           、
           <a href="http://cos.name/category/data/dmml/" rel="category tag">
            数据挖掘与机器学习
           </a>
          </span>
          <span class="tags-links">
           <a href="http://cos.name/tag/duality/" rel="tag">
            Duality
           </a>
           、
           <a href="http://cos.name/tag/%e6%94%af%e6%8c%81%e5%90%91%e9%87%8f%e6%9c%ba/" rel="tag">
            支持向量机
           </a>
           、
           <a href="http://cos.name/tag/%e6%9c%ba%e5%99%a8%e5%ad%a6%e4%b9%a0/" rel="tag">
            机器学习
           </a>
          </span>
          <span class="author vcard">
           <a class="url fn n" href="http://cos.name/author/chiyuan/" rel="author" title="查看所有由张 驰原发布的文章">
            张 驰原
           </a>
          </span>
         </div>
         <!-- .entry-meta -->
        </header>
        <!-- .entry-header -->
        <div class="entry-content">
         <p>
          <i>
           原文链接请点击
           <a href="http://blog.pluskid.org/?p=702" target="_blank">
            这里
           </a>
          </i>
         </p>
         <p>
          在
          <a href="http://cos.name/?p=682">
           之前关于 support vector 的推导
          </a>
          中，我们提到了 dual ，这里再来补充一点相关的知识。这套理论不仅适用于 SVM 的优化问题，而是对于所有带约束的优化问题都适用的，是优化理论中的一个重要部分。简单来说，对于任意一个带约束的优化都可以写成这样的形式：
         </p>
         <p>
          \[
          <br/>
          \begin{aligned}
          <br/>
          \min&amp;f_0(x) \\
          <br/>
          s.t. &amp;f_i(x)\leq 0, \quad i=1,\ldots,m\\
          <br/>
          &amp;h_i(x)=0, \quad i=1,\ldots,p
          <br/>
          \end{aligned}
          <br/>
          \]
         </p>
         <p>
          形式统一能够简化推导过程中不必要的复杂性。其他的形式都可以归约到这样的标准形式，例如一个 $\max f(x)$ 可以转化为 $\min -f(x)$ 等。假如 $f_0,f_1,\ldots,f_m$ 全都是
          <a href="http://en.wikipedia.org/wiki/Convex_function">
           凸函数
          </a>
          ，并且 $h_1,\ldots,h_p$ 全都是
          <a href="http://en.wikipedia.org/wiki/Affine_function">
           仿射函数
          </a>
          （就是形如 $Ax+b$ 的形式），那么这个问题就叫做凸优化（Convex Optimization）问题。凸优化问题有许多优良的性质，例如它的极值是唯一的。不过，这里我们并没有假定需要处理的优化问题是一个凸优化问题。
         </p>
         <p>
          <span id="more-9682">
          </span>
          虽然约束条件能够帮助我们减小搜索空间，但是如果约束条件本身就是比较复杂的形式的话，其实是一件很让人头痛的问题，为此我们希望把带约束的优化问题转化为无约束的优化问题。为此，我们定义 Lagrangian 如下：
         </p>
         <p>
          \[
          <br/>
          L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^p\nu_ih_i(x)
          <br/>
          \]
         </p>
         <p>
          它通过一些系数把约束条件和目标函数结合在了一起。当然 Lagrangian 本身并不好玩，现在让我们来让他针对 $\lambda$ 和 $\nu$ 最大化，令：
         </p>
         <p>
          \[
          <br/>
          z(x)=\max_{\lambda\succeq 0, \nu}L(x,\lambda,\nu)
          <br/>
          \]
         </p>
         <p>
          这里 $\lambda\succeq 0$ 理解为向量 $\lambda$ 的每一个元素都非负即可。这个函数 $z(x)$ 对于满足原始问题约束条件的那些 $x$ 来说，其值等于 $f_0(x)$ ，这很容易验证，因为满足约束条件的 $x$ 会使得 $h_i(x)=0$ ，因此最后一项消掉了，而 $f_i(x)\leq 0$ ，并且我们要求了 $\lambda \succeq 0$ ，因此 $\lambda_if_i(x)\leq 0$ ，所以最大值只能在它们都取零的时候得到，这个时候就只剩下 $f_0(x)$ 了。因此，对于满足约束条件的那些 $x$ 来说，$f_0(x)=z(x)$ 。这样一来，原始的带约束的优化问题其实等价于如下的无约束优化问题：
         </p>
         <p>
          \[
          <br/>
          \min_x z(x)
          <br/>
          \]
         </p>
         <p>
          因为如果原始问题有最优值，那么肯定是在满足约束条件的某个 $x^*$ 取得，而对于所有满足约束条件的 $x$ ，$z(x)$ 和 $f_0(x)$ 都是相等的。至于那些不满足约束条件的 $x$ ，原始问题是无法取到的，否则极值问题无解。很容易验证对于这些不满足约束条件的 $x$ 有 $z(x)=\infty$，这也和原始问题是一致的，因为求最小值得到无穷大可以和“无解”看作是相容的。
         </p>
         <p>
          到这里，我们成功把带约束问题转化为了无约束问题，不过这其实只是一个形式上的重写，并没有什么本质上的改变。我们只是把原来的问题通过 Lagrangian 写作了如下形式：
         </p>
         <p>
          \[
          <br/>
          \min_x\ \max_{\lambda\succeq 0, \nu} L(x, \lambda, \nu)
          <br/>
          \]
         </p>
         <p>
          这个问题（或者说原始的带约束的形式）称作 primal problem 。如果你看过之前关于 SVM 的推导，那么肯定就知道了，相对应的还有一个 dual problem ，其形式非常类似，只是把 $\min$ 和 $\max$ 交换了一下：
         </p>
         <p>
          \[
          <br/>
          \max_{\lambda\succeq 0, \nu}\ \min_x L(x, \lambda, \nu)
          <br/>
          \]
         </p>
         <p>
          交换之后的 dual problem 和原来的 primal problem 并不相等，直观地，我们可以这样来理解：胖子中最瘦的那个都比瘦骨精中最胖的那个要胖。当然这是很不严格的说法，而且扣字眼的话可以纠缠不休，所以我们还是来看严格数学描述。和刚才的 $z(x)$ 类似，我们也用一个记号来表示内层的这个函数，记：
         </p>
         <p>
          \[
          <br/>
          g(\lambda,\nu) = \min_x L(x, \lambda, \nu)
          <br/>
          \]
         </p>
         <p>
          并称 $g(\lambda,\nu)$ 为 Lagrange dual function （不要和 $L$ 的 Lagrangian 混淆了）。$g$ 有一个很好的性质就是它是 primal problem 的一个下界。换句话说，如果 primal problem 的最小值记为 $p^*$ ，那么对于所有的 $\lambda \succeq 0$ 和 $\nu$ ，我们有：
         </p>
         <p>
          \[
          <br/>
          g(\lambda,\nu)\leq p^*
          <br/>
          \]
         </p>
         <p>
          因为对于极值点（实际上包括所有满足约束条件的点）$x^*$，注意到 $\lambda\succeq 0$ ，我们总是有
         </p>
         <p>
          \[
          <br/>
          \sum_{i=1}^m\lambda_if_i(x^*)+\sum_{i=1}^p\nu_ih_i(x^*)\leq 0
          <br/>
          \]
         </p>
         <p>
          因此
         </p>
         <p>
          \[
          <br/>
          L(x^*,\lambda,\nu)=f_0(x^*)+\sum_{i=1}^m\lambda_if_i(x^*)+\sum_{i=1}^p\nu_ih_i(x^*)\leq f_0(x^*)
          <br/>
          \]
         </p>
         <p>
          于是
         </p>
         <p>
          \[
          <br/>
          g(\lambda,\nu)=\min_x L(x,\lambda,\nu)\leq L(x^*,\lambda,\nu)\leq f_0(x^*)=p^*
          <br/>
          \]
         </p>
         <p>
          这样一来就确定了 $g$ 的下界性质，于是
         </p>
         <p>
          \[
          <br/>
          \max_{\lambda\succeq 0,\nu}g(\lambda,\nu)
          <br/>
          \]
         </p>
         <p>
          实际上就是最大的下界。这是很自然的，因为得到下界之后，我们自然地就希望得到最好的下界，也就是最大的那一个——因为它离我们要逼近的值最近呀。记 dual problem 的最优值为 $d^*$ 的话，根据上面的推导，我们就得到了如下性质：
         </p>
         <p>
          \[
          <br/>
          d^*\leq p^*
          <br/>
          \]
         </p>
         <p>
          这个性质叫做 weak duality ，对于所有的优化问题都成立。其中 $p^*-d^*$ 被称作 duality gap 。需要注意的是，无论 primal problem 是什么形式，dual problem 总是一个 convex optimization 的问题——它的极值是唯一的（如果存在的话），并且有现成的软件包可以对凸优化问题进行求解（虽然求解 general 的 convex optimization 实际上是很慢并且只能求解规模较小的问题的）。这样一来，对于那些难以求解的 primal problem （比如，甚至可以是 NP 问题），我们可以通过找出它的 dual problem ，通过优化这个 dual problem 来得到原始问题的一个下界估计。或者说我们甚至都不用去优化这个 dual problem ，而是（通过某些方法，例如随机）选取一些 $\lambda\succeq 0$ 和 $\nu$ ，带到 $g(\lambda,\nu)$ 中，这样也会得到一些下界（只不过不一定是最大的那个下界而已）。当然要选 $\lambda$ 和 $\nu$ 也并不是总是“随机选”那么容易，根据具体问题，有时候选出来的 $\lambda$ 和 $\nu$ 带入 $g$ 会得到 $-\infty$ ，这虽然是一个完全合法的下界，然而却并没有给我们带来任何有用的信息。
         </p>
         <p>
          故事到这里还没有结束，既然有 weak duality ，显然就会有 strong duality 。所谓 strong duality ，就是
         </p>
         <p>
          \[
          <br/>
          d^*=p^*
          <br/>
          \]
         </p>
         <p>
          这是一个很好的性质，strong duality 成立的情况下，我们可以通过求解 dual problem 来优化 primal problem ，在 SVM 中我们就是这样做的。当然并不是所有的问题都能满足 strong duality ，在讲 SVM 的时候我们直接假定了 strong duality 的成立，这里我们就来提一下 strong duality 成立的条件。不过，这个问题如果要讲清楚，估计写一本书都不够，应该也有不少专门做优化方面的人在研究这相关的问题吧，我没有兴趣（当然也没有精力和能力）来做一个完整的介绍，相信大家也没有兴趣来看这样的东西——否则你肯定是专门研究优化方面的问题的了，此时你肯定比我懂得更多，也就不用看我写的介绍啦。 :p
         </p>
         <p>
          所以，这里我们就简要地介绍一下 Slater 条件和 KKT 条件。Slater 条件是指存在严格满足约束条件的点 $x$ ，这里的“严格”是指 $f_i(x)\leq 0$ 中的“小于或等于号”要严格取到“小于号”，亦即，存在 $x$ 满足
         </p>
         <p>
          \[
          <br/>
          \begin{aligned}
          <br/>
          f_i(x)&lt;0&amp;\quad i=1,\ldots,m\\
          <br/>
          h_i(x)=0&amp;\quad i=1,\ldots,p
          <br/>
          \end{aligned}
          <br/>
          \]
         </p>
         <p>
          我们有：如果原始问题是 Convex 的并且满足 Slater 条件的话，那么 strong duality 成立。需要注意的是，这里只是指出了 strong duality 成立的一种情况，而并不是唯一情况。例如，对于某些非 convex optimization 的问题，strong duality 也成立。这里我们不妨回顾一下 SVM 的 primal problem ，那是一个 convex optimization 问题（QP 是凸优化问题的一种特殊情况），而 Slater 条件实际上在这里就等价于是存在这样的一个超平面将数据分隔开来，亦即是“数据是可分的”。当数据不可分是，strong duality 不能成立，不过，这个时候我们寻找分隔平面这个问题本身也就是没有意义的了，至于我们如何通过把数据映射到特征空间中来解决不可分的问题，这个当时
          <a href="http://cos.name/?p=685">
           已经介绍过了
          </a>
          ，这里就不多说了。
         </p>
         <p>
          让我们回到 duality 的话题。来看看 strong duality 成立的时候的一些性质。假设 $x^*$ 和 $(\lambda^*,\nu^*)$ 分别是 primal problem 和 dual problem 的极值点，相应的极值为 $p^*$ 和 $d^*$ ，首先 $p^*=d^*$ ，此时我们可以得到
         </p>
         <p>
          \[
          <br/>
          \begin{aligned}
          <br/>
          f_0(x^*)&amp;=g(\lambda^*,\nu^*)\\
          <br/>
          &amp;=\min_x\left(f_0(x)+\sum_{i=1}^m\lambda_i^*f_i(x)+\sum_{i=1}^p\nu_i^*h_i(x)\right)\\
          <br/>
          &amp;\leq f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{i=1}^p\nu_i^*h_i(x^*) \\
          <br/>
          &amp;\leq f_0(x^*)
          <br/>
          \end{aligned}
          <br/>
          \]
         </p>
         <p>
          由于两头是相等的，所以这一系列的式子里的不等号全部都可以换成等号。根据第一个不等号我们可以得到 $x^*$ 是 $L(x,\lambda^*,\nu^*)$ 的一个极值点，由此可以知道 $L(x,\lambda^*,\nu^*)$ 在 $x^*$ 处的梯度应该等于 0 ，亦即：
         </p>
         <p>
          \[
          <br/>
          \nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x^*)+\sum_{i=1}^p\nu_i^* \nabla h_i(x^*)=0
          <br/>
          \]
         </p>
         <p>
          此外，由第二个不等式，又显然 $\lambda_i^*f_i(x^*)$ 都是非正的，因此我们可以得到
         </p>
         <p>
          \[
          <br/>
          \lambda_i^*f_i(x^*)=0,\quad i=1,\ldots,m
          <br/>
          \]
         </p>
         <p>
          这个条件叫做 complementary slackness 。显然，如果 $\lambda_i^*&gt;0$，那么必定有 $f_i(x^*)=0$ ；反过来，如果 $f_i(x^*)&lt;0$ 那么可以得到 $\lambda_i^*=0$ 。这个条件正是我们在
          <a href="http://cos.name/?p=682">
           介绍支持向量的文章
          </a>
          末尾时用来证明那些非支持向量（对应于 $f_i(x^*)&lt;0$）所对应的系数 $\alpha_i$ （在本文里对应 $\lambda_i$ ）是为零的。 🙂
         </p>
         <p>
          再将其他一些显而易见的条件写到一起，就是传说中的 KKT (Karush-Kuhn-Tucker) 条件：
         </p>
         <p>
          \[
          <br/>
          \begin{aligned}
          <br/>
          f_i(x^*)\leq 0,&amp;\quad i=1,\ldots,m\\
          <br/>
          h_i(x^*)=0,&amp;\quad i=1,\ldots,p\\
          <br/>
          \lambda_i^*\geq 0,&amp;\quad i=1,\ldots,m\\
          <br/>
          \lambda_i^*f_i(x^*)=0,&amp;\quad i=1,\ldots,m\\
          <br/>
          \textstyle\nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x^*)+\sum_{i=1}^p\nu_i^* \nabla h_i(x^*)=0&amp;
          <br/>
          \end{aligned}
          <br/>
          \]
         </p>
         <p>
          任何满足 strong duality （不一定要求是通过 Slater 条件得到，也不一定要求是凸优化问题）的问题都满足 KKT 条件，换句话说，这是 strong duality 的一个必要条件。不过，当原始问题是凸优化问题的时候（当然还要求一应函数是可微的，否则 KKT 条件的最后一个式子就没有意义了），KKT 就可以升级为充要条件。换句话说，如果 primal problem 是一个凸优化问题，且存在 $\tilde{x}$ 和 $(\tilde{\lambda},\tilde{\nu})$ 满足 KKT 条件，那么它们分别是 primal problem 和 dual problem 的极值点并且 strong duality 成立。
         </p>
         <p>
          其证明也比较简单，首先 primal problem 是凸优化问题的话，$g(\lambda,\nu)=\min_x L(x,\lambda,\nu)$ 的求解对每一组固定的 $(\lambda,\nu)$ 来说也是一个凸优化问题，由 KKT 条件的最后一个式子，知道 $\tilde{x}$ 是 $\min_x L(x,\tilde{\lambda},\tilde{\nu})$ 的极值点（如果不是凸优化问题，则不一定能推出来），亦即：
         </p>
         <p>
          \[
          <br/>
          \begin{aligned}
          <br/>
          g(\tilde{\lambda},\tilde{\nu}) &amp;= \min_x L(x,\tilde{\lambda},\tilde{\nu}) \\
          <br/>
          &amp;= L(\tilde{x},\tilde{\lambda},\tilde{\nu}) \\
          <br/>
          &amp; = f_0(\tilde{x})+\sum_{i=1}^m\tilde{\lambda}_i^*f_i(\tilde{x})+\sum_{i=1}^p\tilde{\nu_i}^*h_i(\tilde{x}) \\
          <br/>
          &amp;= f_0(\tilde{x})
          <br/>
          \end{aligned}
          <br/>
          \]
         </p>
         <p>
          最后一个式子是根据 KKT 条件的第二和第四个条件得到。由于 $g$ 是 $f_0$ 的下界，这样一来，就证明了 duality gap 为零，也就是说，strong duality 成立。
         </p>
         <p>
          到此为止，做一下总结。我们简要地介绍了 duality 的概念，基本上没有给什么具体的例子。不过由于内容比较多，为了避免文章超长，就挑了一些重点讲了一下。总的来说，一个优化问题，通过求出它的 dual problem ，在只有 weak duality 成立的情况下，我们至少可以得到原始问题的一个下界。而如果 strong duality 成立，则可以直接求解 dual problem 来解决原始问题，就如同经典的 SVM 的求解过程一样。有可能 dual problem 比 primal problem 更容易求解，或者 dual problem 有一些优良的结构（例如 SVM 中通过 dual problem 我们可以将问题表示成数据的内积形式从而使得 kernel trick 的应用成为可能）。此外，还有一些情况会同时求解 dual 和 primal problem ，比如在迭代求解的过程中，通过判断 duality gap 的大小，可以得出一个有效的迭代停止条件。
         </p>
         <div class="wumii-hook">
          <br/>
          <br/>
         </div>
        </div>
        <!-- .entry-content -->
        <footer class="entry-meta">
         <div class="author-info">
          <div class="author-avatar">
           <img src="http://sdn.geekzu.org/avatar/7d77289b052ce9a485b025f34f1368ff?s=74&amp;d=monsterid&amp;r=g"/>
          </div>
          <!-- .author-avatar -->
          <div class="author-description">
           <h2 class="author-title">
            关于张 驰原
           </h2>
           <p class="author-bio">
            PhD Candidate in EECS Department, MIT
            <a class="author-link" href="http://cos.name/author/chiyuan/" rel="author">
             查看所有由张 驰原发表的文章
             <span class="meta-nav">
              →
             </span>
            </a>
           </p>
          </div>
          <!-- .author-description -->
         </div>
         <!-- .author-info -->
        </footer>
        <!-- .entry-meta -->
       </article>
       <!-- #post -->
       <nav class="navigation post-navigation" role="navigation">
        <h1 class="screen-reader-text">
         文章导航
        </h1>
        <div class="nav-links">
         <a href="http://cos.name/2014/03/lets-talk-about-money/" rel="prev">
          <span class="meta-nav">
           ←
          </span>
          COS每周精选：谈钱不伤感情
         </a>
         <a href="http://cos.name/2014/04/7th-r-conference-beijing/" rel="next">
          第七届中国R语言会议（北京会场）通知
          <span class="meta-nav">
           →
          </span>
         </a>
        </div>
        <!-- .nav-links -->
       </nav>
       <!-- .navigation -->
       <div class="comments-area" id="comments">
        <h2 class="comments-title">
         《
         <span>
          “支持向量机系列”的番外篇一: Duality
         </span>
         》有2个想法
        </h2>
        <ol class="comment-list">
         <li class="comment even thread-even depth-1" id="comment-5600">
          <article class="comment-body" id="div-comment-5600">
           <footer class="comment-meta">
            <div class="comment-author vcard">
             <img src="http://sdn.geekzu.org/avatar/?s=74&amp;d=monsterid&amp;r=g"/>
             <b class="fn">
              <a class="url" href="http://weibo.com/1911882687" rel="external nofollow">
               九生有幸
              </a>
             </b>
             <span class="says">
              说道：
             </span>
            </div>
            <!-- .comment-author -->
            <div class="comment-metadata">
             <a href="http://cos.name/2014/03/svm-series-add-1-duality/#comment-5600">
              <time datetime="2014-04-26T20:03:38+00:00">
               2014/04/26 20:03
              </time>
             </a>
            </div>
            <!-- .comment-metadata -->
           </footer>
           <!-- .comment-meta -->
           <div class="comment-content">
            <p>
             你好，非常感谢写出这么精彩的文章！关于SVM我现在有个疑问，SVM本质是解一个优化问题，但是这个优化问题的表达式却有多种，一种就是你在这系列文章4中给出的形式，我还看到一种就是最小化损失函数(loss function)，具体写出来就是w* = argmin frac{lambda}{2} ||w||^2 + frac{1}{n} Sigma_1^n l(w, x_i, y_i)，其中l是loss funcion， lambda是惩罚系数。 对于这两种形式的优化问题，解应该是不一样的，我想问的是这两种形式的SVM的适用范围各是什么或者说优缺点是什么？或者再问得广一点，SVM所有的优化形式之间的区别与联系是什么？具体到现实问题之中，是否有某个先知的指导原则告诉我们应该选哪种优化形式？ 谢谢！
            </p>
           </div>
           <!-- .comment-content -->
           <div class="reply">
            <a aria-label="回复给九生有幸" class="comment-reply-link" href="http://cos.name/2014/03/svm-series-add-1-duality/?replytocom=5600#respond" onclick='return addComment.moveForm( "div-comment-5600", "5600", "respond", "9682" )' rel="nofollow">
             回复
            </a>
           </div>
          </article>
          <!-- .comment-body -->
         </li>
         <!-- #comment-## -->
         <li class="comment odd alt thread-odd thread-alt depth-1" id="comment-5623">
          <article class="comment-body" id="div-comment-5623">
           <footer class="comment-meta">
            <div class="comment-author vcard">
             <img src="http://sdn.geekzu.org/avatar/6e39d0d513d4c32e4ce2ba333620dc00?s=74&amp;d=monsterid&amp;r=g"/>
             <b class="fn">
              <a class="url" href="http://www.zhouleyu.com/life/skinny-essential-oils-work-again" rel="external nofollow">
               zhouleyu
              </a>
             </b>
             <span class="says">
              说道：
             </span>
            </div>
            <!-- .comment-author -->
            <div class="comment-metadata">
             <a href="http://cos.name/2014/03/svm-series-add-1-duality/#comment-5623">
              <time datetime="2014-04-30T13:12:13+00:00">
               2014/04/30 13:12
              </time>
             </a>
            </div>
            <!-- .comment-metadata -->
           </footer>
           <!-- .comment-meta -->
           <div class="comment-content">
            <p>
             你好，非常感谢写出这么精彩的文章！关于SVM我现在有个疑问，SVM本质是解一个优化问题，但是这个优化问题的表达式却有多种，一种就是你在这系列文章4中给出的形式，我还看到一种就是最小化损失函数(loss
            </p>
           </div>
           <!-- .comment-content -->
           <div class="reply">
            <a aria-label="回复给zhouleyu" class="comment-reply-link" href="http://cos.name/2014/03/svm-series-add-1-duality/?replytocom=5623#respond" onclick='return addComment.moveForm( "div-comment-5623", "5623", "respond", "9682" )' rel="nofollow">
             回复
            </a>
           </div>
          </article>
          <!-- .comment-body -->
         </li>
         <!-- #comment-## -->
        </ol>
        <!-- .comment-list -->
        <div class="comment-respond" id="respond">
         <h3 class="comment-reply-title" id="reply-title">
          发表评论
          <small>
           <a href="http://cos.name/2014/03/svm-series-add-1-duality/#respond" id="cancel-comment-reply-link" rel="nofollow" style="display:none;">
            取消回复
           </a>
          </small>
         </h3>
         <form action="http://cos.name/wp-comments-post.php" class="comment-form" id="commentform" method="post" novalidate="">
          <p class="comment-notes">
           <span id="email-notes">
            电子邮件地址不会被公开。
           </span>
           必填项已用
           <span class="required">
            *
           </span>
           标注
          </p>
          <p class="comment-form-comment">
           <label for="comment">
            评论
           </label>
           <textarea aria-required="true" cols="45" id="comment" maxlength="65525" name="comment" required="required" rows="8">
           </textarea>
          </p>
          <p class="comment-form-author">
           <label for="author">
            姓名
            <span class="required">
             *
            </span>
           </label>
          </p>
          <p class="comment-form-email">
           <label for="email">
            电子邮件
            <span class="required">
             *
            </span>
           </label>
          </p>
          <p class="comment-form-url">
           <label for="url">
            站点
           </label>
          </p>
          <p class="form-submit">
          </p>
          <p style="display: none;">
          </p>
          <p style="display: none;">
          </p>
         </form>
        </div>
        <!-- #respond -->
       </div>
       <!-- #comments -->
      </div>
      <!-- #content -->
     </div>
     <!-- #primary -->
     <div class="sidebar-container" id="tertiary" role="complementary">
      <div class="sidebar-inner">
       <div class="widget-area">
        <aside class="widget widget_text" id="text-3">
         <h3 class="widget-title">
          关注统计之都
         </h3>
         <div class="textwidget">
          <ul>
           <li>
            新浪微博
            <a href="http://weibo.com/cosname">
             @统计之都
            </a>
           </li>
           <li>
            人人网
            <a href="http://renren.com/cosname">
             @统计之都
            </a>
           </li>
           <li>
            Twitter
            <a href="http://twitter.com/cos_name">
             @cos_name
            </a>
           </li>
          </ul>
         </div>
        </aside>
        <aside class="widget widget_text" id="text-6">
         <h3 class="widget-title">
          微信公众平台
         </h3>
         <div class="textwidget">
          <img src="http://cos.name/wp-content/uploads/2013/04/qrcode-8cm.jpg"/>
          <p style="font-size:12px;margin-left:15px">
           微信号 CapStat
          </p>
          <p>
           我们将第一时间向您推送主站和论坛的精彩内容，以及统计之都的线下活动、竞赛、培训和会议信息。
          </p>
         </div>
        </aside>
        <aside class="widget widget_text" id="text-8">
         <h3 class="widget-title">
          站内导航
         </h3>
         <div class="textwidget">
          <ul>
           <li class="page_item">
            <a href="http://cos.name/cn/">
             中文论坛
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/videos/">
             视频
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/salon/">
             统计沙龙
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/books/">
             图书出版
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/training/">
             教育培训
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/about/">
             关于我们
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/donate/">
             捐赠
            </a>
           </li>
           <li class="page_item">
            <a href="http://cos.name/chinar/">
             R语言会议
            </a>
           </li>
          </ul>
         </div>
        </aside>
        <aside class="widget widget_links" id="linkcat-2">
         <h3 class="widget-title">
          友情链接
         </h3>
         <ul class="xoxo blogroll">
          <li>
           <a href="http://stat.ruc.edu.cn" target="_blank" title="中国人民大学统计学院网站">
            中国人民大学统计学院
           </a>
          </li>
          <li>
           <a href="http://rucdmc.net">
            中国人民大学数据挖掘中心
           </a>
          </li>
          <li>
           <a href="http://birc.gsm.pku.edu.cn/" target="_blank">
            北京大学商务智能研究中心
           </a>
          </li>
          <li>
           <a href="http://sam.cufe.edu.cn/" target="_blank" title="中央财经大学统计与数学学院网站">
            中央财经大学统计与数学学院
           </a>
          </li>
          <li>
           <a href="http://tjx.cueb.edu.cn/" target="_blank" title="首都经济贸易大学统计学院网站">
            首经贸统计学院
           </a>
          </li>
          <li>
           <a href="http://www.shookr.com/">
            数客网大数据社区
           </a>
          </li>
          <li>
           <a href="http://www.xueqing.tv/" target="_blank" title="数据科学在线学习平台">
            雪晴数据网
           </a>
          </li>
          <li>
           <a href="http://iera.name/" target="_blank" title="IERA是一个旨在普及、传播和增进工业工程知识的非营利性网站">
            IERA（直通IE）
           </a>
          </li>
         </ul>
        </aside>
        <aside class="widget widget_categories" id="categories-2">
         <h3 class="widget-title">
          全部分类
         </h3>
         <label class="screen-reader-text" for="cat">
          全部分类
         </label>
         <select class="postform" id="cat" name="cat">
          <option value="-1">
           选择分类目录
          </option>
          <option class="level-0" value="925">
           cos访谈  (4)
          </option>
          <option class="level-0" value="659">
           图书出版  (5)
          </option>
          <option class="level-0" value="379">
           数学方法  (14)
          </option>
          <option class="level-1" value="381">
           分析与代数  (1)
          </option>
          <option class="level-1" value="380">
           概率论  (9)
          </option>
          <option class="level-1" value="382">
           随机过程  (5)
          </option>
          <option class="level-0" value="210">
           数据分析  (81)
          </option>
          <option class="level-1" value="203">
           多元统计  (3)
          </option>
          <option class="level-1" value="42">
           数据挖掘与机器学习  (42)
          </option>
          <option class="level-1" value="36">
           生物与医学统计  (17)
          </option>
          <option class="level-1" value="35">
           计量经济学  (4)
          </option>
          <option class="level-1" value="296">
           金融统计  (3)
          </option>
          <option class="level-1" value="303">
           风险精算  (7)
          </option>
          <option class="level-0" value="177">
           模型专题  (15)
          </option>
          <option class="level-1" value="38">
           回归分析  (10)
          </option>
          <option class="level-1" value="41">
           时间序列  (2)
          </option>
          <option class="level-0" value="784">
           每周精选  (24)
          </option>
          <option class="level-1" value="183">
           可视化  (9)
          </option>
          <option class="level-0" value="967">
           沙龙纪要  (3)
          </option>
          <option class="level-0" value="18">
           经典理论  (46)
          </option>
          <option class="level-1" value="37">
           抽样调查  (3)
          </option>
          <option class="level-1" value="4">
           统计推断  (26)
          </option>
          <option class="level-1" value="236">
           试验设计  (7)
          </option>
          <option class="level-1" value="39">
           非参数统计  (3)
          </option>
          <option class="level-0" value="1">
           统计之都  (279)
          </option>
          <option class="level-1" value="884">
           中国R会议  (2)
          </option>
          <option class="level-1" value="885">
           中国R语言会议  (5)
          </option>
          <option class="level-1" value="446">
           出国留学  (3)
          </option>
          <option class="level-1" value="179">
           推荐文章  (90)
          </option>
          <option class="level-1" value="3">
           新闻通知  (75)
          </option>
          <option class="level-1" value="263">
           统计刊物  (10)
          </option>
          <option class="level-1" value="174">
           网站导读  (40)
          </option>
          <option class="level-1" value="204">
           职业事业  (51)
          </option>
          <option class="level-1" value="213">
           高校课堂  (9)
          </option>
          <option class="level-0" value="178">
           统计计算  (28)
          </option>
          <option class="level-1" value="40">
           优化与模拟  (15)
          </option>
          <option class="level-1" value="43">
           贝叶斯方法  (6)
          </option>
          <option class="level-0" value="378">
           软件应用  (116)
          </option>
          <option class="level-1" value="44">
           统计图形  (36)
          </option>
          <option class="level-1" value="110">
           统计软件  (83)
          </option>
         </select>
        </aside>
        <aside class="widget widget_recent_comments" id="recent-comments-2">
         <h3 class="widget-title">
          最新评论
         </h3>
         <ul id="recentcomments">
          <li class="recentcomments">
           <span class="comment-author-link">
            fineboom
           </span>
           发表在《
           <a href="http://cos.name/2016/06/use-shiny-fleetly-set-up-visual-prototype-system/#comment-7317">
            利用shiny包快速搭建可视化原型系统
           </a>
           》
          </li>
          <li class="recentcomments">
           <span class="comment-author-link">
            胡家新
           </span>
           发表在《
           <a href="http://cos.name/2016/06/r%e8%af%ad%e5%8d%83%e5%af%bb%e7%ac%ac%e4%b8%89%e6%9c%9f%ef%bc%9a%e5%bc%a0%e6%97%a0%e5%bf%8c%e7%a9%b6%e7%ab%9f%e7%88%b1%e8%b0%81%ef%bc%9f/#comment-7316">
            R语千寻第三期：张无忌究竟爱谁？
           </a>
           》
          </li>
          <li class="recentcomments">
           <span class="comment-author-link">
            <a class="url" href="http://www.zijiacha.com/category.php?id=6" rel="external nofollow">
             南糯山普洱茶
            </a>
           </span>
           发表在《
           <a href="http://cos.name/2016/06/r%e8%af%ad%e5%8d%83%e5%af%bb%e7%ac%ac%e4%b8%89%e6%9c%9f%ef%bc%9a%e5%bc%a0%e6%97%a0%e5%bf%8c%e7%a9%b6%e7%ab%9f%e7%88%b1%e8%b0%81%ef%bc%9f/#comment-7315">
            R语千寻第三期：张无忌究竟爱谁？
           </a>
           》
          </li>
          <li class="recentcomments">
           <span class="comment-author-link">
            J
           </span>
           发表在《
           <a href="http://cos.name/2016/05/value-of-the-reputation-from-the-data/#comment-7314">
            数据告诉你：高信誉的卖家应该收高价，还是收低价？
           </a>
           》
          </li>
          <li class="recentcomments">
           <span class="comment-author-link">
            <a class="url" href="http://gg" rel="external nofollow">
             Hilda
            </a>
           </span>
           发表在《
           <a href="http://cos.name/2013/01/drawing-map-in-r-era/#comment-7311">
            R时代，你要怎样画地图？
           </a>
           》
          </li>
         </ul>
        </aside>
        <aside class="widget widget_rss" id="rss-282869971">
         <h3 class="widget-title">
          <a class="rsswidget" href="http://cos.name/cn/topics/feed/">
           <img src="http://cos.name/wp-includes/images/rss.png"/>
          </a>
          <a class="rsswidget" href="http://cos.name/cn/topics/feed/">
           中文论坛新帖
          </a>
         </h3>
         <ul>
          <li>
           <a class="rsswidget" href="http://cos.name/cn/topic/417372/">
            处理时间数据和产生时间序列的问题
           </a>
          </li>
          <li>
           <a class="rsswidget" href="http://cos.name/cn/topic/6790/">
            《统计陷阱》下载 （How to lie with statistics）
           </a>
          </li>
          <li>
           <a class="rsswidget" href="http://cos.name/cn/topic/818/">
            统计学的世界（第五版）
           </a>
          </li>
          <li>
           <a class="rsswidget" href="http://cos.name/cn/topic/16574/">
            class(x) 返回值值是AsIs,AsIs代表什么，有什么用处？
           </a>
          </li>
          <li>
           <a class="rsswidget" href="http://cos.name/cn/topic/417366/">
            如何用R绘制一个分类算法的决策规则
           </a>
          </li>
         </ul>
        </aside>
        <aside class="widget widget_text" id="text-2">
         <h3 class="widget-title">
          登录/RSS
         </h3>
         <div class="textwidget">
          <ul>
           <li>
            <a href="http://cos.name/wp-admin/">
             登录
            </a>
           </li>
           <li>
            <a href="http://cos.name/feed/" title="使用 RSS 2.0 同步站点内容">
             文章
             <abbr title="Really Simple Syndication">
              RSS
             </abbr>
            </a>
           </li>
           <li>
            <a href="http://cos.name/comments/feed/" title="RSS 上的最近评论">
             评论
             <abbr title="Really Simple Syndication">
              RSS
             </abbr>
            </a>
           </li>
          </ul>
         </div>
        </aside>
       </div>
       <!-- .widget-area -->
      </div>
      <!-- .sidebar-inner -->
     </div>
     <!-- #tertiary -->
    </div>
    <!-- #main -->
    <footer class="site-footer" id="colophon" role="contentinfo">
     <div class="site-info">
      版权所有 © 2014 统计之都 | 由
      <a href="http://wordpress.org/">
       WordPress
      </a>
      构建 | 主题修改自
      <a href="http://wordpress.org/themes/twentythirteen">
       Twenty Thirteen
      </a>
     </div>
     <!-- .site-info -->
    </footer>
    <!-- #colophon -->
   </div>
   <!-- #page -->
   <p style="margin:0;padding:0;height:1px;overflow:hidden;">
    <a href="http://www.wumii.com/widget/relatedItems" style="border:0;">
     <img src="http://static.wumii.cn/images/pixel.png"/>
    </a>
   </p>
  </div>
 </body>
</html>